package leetcode.N401_N500;

import java.util.HashMap;
import java.util.Map;

public class N496 {

    public static void main(String[] args) {
        int[] nums1 = {4,1,2};
        int[] nums2 = {1,3,4,2};
        System.out.println(nextGreaterElement(nums1, nums2));
    }

    static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        if (nums1.length == 0) {
            return nums1;
        }
        int [] stack = new int[nums2.length];
        int index = 0;
        Map<Integer, Integer> biggerMapping = new HashMap<>();
        stack[index] = nums2[index++];

        for (int i = 1; i < nums2.length; i++) {
            int num2 = nums2[i];
            for (int k = index - 1; k >= 0; k--) {
                int temp = stack[k];
                if (temp < num2) {
                    // 保存数字与下标的映射关系
                    biggerMapping.put(temp, i);
                    // 将栈顶元素弹出
                    index--;
                }
            }
            stack[index++] = num2;
        }


        for (int i = 0; i < nums1.length; i++) {
            nums1[i] = biggerMapping.get(nums1[i]) == null ? -1 : nums2[biggerMapping.get(nums1[i])];
        }
        return nums1;
    }
}
